package leetcode.editor.cn.dsa02_linkedlist;
//对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
//
// 给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 输入：A = [1,2,0,0], K = 34
//输出：[1,2,3,4]
//解释：1200 + 34 = 1234
// 
//
// 示例 2： 
//
// 输入：A = [2,7,4], K = 181
//输出：[4,5,5]
//解释：274 + 181 = 455
// 
//
// 示例 3： 
//
// 输入：A = [2,1,5], K = 806
//输出：[1,0,2,1]
//解释：215 + 806 = 1021
// 
//
// 示例 4： 
//
// 输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
//输出：[1,0,0,0,0,0,0,0,0,0,0]
//解释：9999999999 + 1 = 10000000000
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 10000 
// 0 <= A[i] <= 9 
// 0 <= K <= 10000 
// 如果 A.length > 1，那么 A[0] != 0 
// 
// Related Topics 数组 
// 👍 72 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class AddToArrayFormOfInteger989 {
    public static void main(String[] args) {
        Solution solution = new AddToArrayFormOfInteger989().new Solution();
        int[] arr = {99};
        int[] arr2 = {1,2,5,6};
        System.out.println(solution.addToArrayForm(arr, 34));
        System.out.println(solution.addToArrayForm(arr, 1212));
        System.out.println(solution.addToArrayForm(arr, 99999));
        System.out.println(solution.addToArrayForm(arr2, 34));
        System.out.println(solution.addToArrayForm(arr2, 1212));
        System.out.println(solution.addToArrayForm(arr2, 99999));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> addToArrayForm(int[] A, int K) {
            if(K == 0) return Arrays.stream(A).boxed().collect(Collectors.toList());
            List<Integer> list = new ArrayList<>();
            int carry = 0; // 记录进位
            int last = 0; // 末位
            int index = A.length - 1;
            // 取K的每一位与数组对应位置数相加，并记录进位
            while((last = K % 10) != K || index >= 0){
                int num = index >= 0 ? A[index] : 0;
                int sum = num + last + carry;
                list.add(sum % 10);
                carry = sum / 10;
                K = K / 10;
                index--;
            }
            // 说明K的长度>=A.length，处理末位
            if(last != 0){
                list.add((last + carry) % 10);
                if((last + carry) / 10 != 0){
                    list.add((last + carry) / 10);
                }
            }else if(carry != 0){
                list.add(carry);
            }
            Collections.reverse(list);
            return list;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}